{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dynamic Programming\n",
    "+ 分析子问题的重复性\n",
    "+ 子问题进行存储\n",
    "+ Solution 要进行解析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "functools:\n",
    "https://www.jianshu.com/p/178788297a5c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "from collections import defaultdict\n",
    "from functools import wraps\n",
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "original_price = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 35]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "price = defaultdict(int)\n",
    "for i, p in enumerate(original_price):\n",
    "    price[i + 1] = p #多少米对应的价格"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(int,\n",
       "            {1: 1,\n",
       "             2: 5,\n",
       "             3: 8,\n",
       "             4: 9,\n",
       "             5: 10,\n",
       "             6: 17,\n",
       "             7: 17,\n",
       "             8: 20,\n",
       "             9: 24,\n",
       "             10: 30,\n",
       "             11: 35})"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# cal function time\n",
    "def call_time(f, args):\n",
    "    start = time.time()\n",
    "    f(args)\n",
    "    print('used time is {}'.format(time.time() - start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def func_1(n):\n",
    "    for i in range(n):\n",
    "        print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "used time is 0.0010175704956054688\n"
     ]
    }
   ],
   "source": [
    "call_time(func_1, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "function_called_times = defaultdict(int)\n",
    "\n",
    "def get_call_times(func):\n",
    "    @wraps(func)\n",
    "    def _inner(args):\n",
    "        \"\"\"it's inner function\"\"\"\n",
    "        # global function_called_times\n",
    "        function_called_times[func.__name__] += 1\n",
    "        result = func(args)\n",
    "        print(\"function called time is {}\".format(function_called_times[func.__name__]))\n",
    "        return result\n",
    "    return _inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "func_1 = get_call_times(func_1) # 装饰器，得到新的func_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "function called time is 2\n"
     ]
    }
   ],
   "source": [
    "func_1(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "@get_call_times\n",
    "def func_1(n):\n",
    "    \"\"\"\n",
    "    n: input parameter\n",
    "    \"\"\"\n",
    "    for i in range(n):\n",
    "        print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function func_1 in module __main__:\n",
      "\n",
      "func_1(n)\n",
      "    n: input parameter\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(func_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "function called time is 8\n"
     ]
    }
   ],
   "source": [
    "func_1(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "#测试下其他函数\n",
    "@get_call_times\n",
    "def func_slow(n):\n",
    "    for i in range(n):\n",
    "        time.sleep(0.2)\n",
    "        print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "function called time is 1\n"
     ]
    }
   ],
   "source": [
    "func_slow(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ r_n = max(p_n, r_1 + r_{n-1}, r_2 + r_{n-2} ...... r_{n-1} + r_1) $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "#进行存储\n",
    "def memo(func):\n",
    "    cache = {} #缓存\n",
    "    @wraps(func)\n",
    "    def _wrap(n):\n",
    "        if n in cache: result = cache[n] #n如果已经有了，直接返回结果\n",
    "        else:\n",
    "            result = func(n) #接着拆分\n",
    "            cache[n] = result #把结果存进缓存中\n",
    "        return result\n",
    "    return _wrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "@memo\n",
    "def r(n):\n",
    "    max_price, max_split = max([(price[n], 0)] + [[r(i) + r(n - i), i]for i in range(1 ,n)], key=lambda x: x[0])\n",
    "    solution[n] = (n - max_split, max_split)\n",
    "    return max_price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "118"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r(38)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: (1, 0),\n",
       " 2: (2, 0),\n",
       " 3: (3, 0),\n",
       " 4: (2, 2),\n",
       " 5: (3, 2),\n",
       " 6: (6, 0),\n",
       " 7: (6, 1),\n",
       " 8: (6, 2),\n",
       " 9: (6, 3),\n",
       " 10: (10, 0),\n",
       " 11: (11, 0),\n",
       " 12: (11, 1),\n",
       " 13: (11, 2),\n",
       " 14: (11, 3),\n",
       " 15: (13, 2),\n",
       " 16: (14, 2),\n",
       " 17: (11, 6),\n",
       " 18: (17, 1),\n",
       " 19: (17, 2),\n",
       " 20: (17, 3),\n",
       " 21: (11, 10),\n",
       " 22: (11, 11),\n",
       " 23: (22, 1),\n",
       " 24: (22, 2),\n",
       " 25: (22, 3),\n",
       " 26: (24, 2),\n",
       " 27: (25, 2),\n",
       " 28: (22, 6),\n",
       " 29: (28, 1),\n",
       " 30: (28, 2),\n",
       " 31: (28, 3),\n",
       " 32: (22, 10),\n",
       " 33: (22, 11),\n",
       " 34: (33, 1),\n",
       " 35: (33, 2),\n",
       " 36: (33, 3),\n",
       " 37: (35, 2),\n",
       " 38: (36, 2)}"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "#解析 solution\n",
    "def parse_solution(n):\n",
    "    left_split, right_split = solution[n]\n",
    "    if right_split == 0: return [left_split]\n",
    "    return parse_solution(left_split) + parse_solution(right_split)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11, 11, 11, 3, 2]"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parse_solution(38)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Edit Distance\n",
    "\n",
    "https://blog.csdn.net/chichoxian/article/details/53944188\n",
    "\n",
    "编辑距离的作用主要是用来比较两个字符串的相似度的\n",
    "\n",
    "编辑距离，又称Levenshtein距离（莱文斯坦距离也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。\n",
    "\n",
    "PS: 此部分代码完全参照老师的，会按照网上其他示例代码再做深一步的理解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "装饰器用一个有记忆的调用包装一个函数，它可以保存最近maxsize次调用。\n",
    "当使用同样的参数定期调用费时或I/O绑定的函数时，它可以节省时间。\n",
    "'''\n",
    "@lru_cache(maxsize=2**10)\n",
    "def edit_distance(string1, string2):\n",
    "    if len(string1) == 0: return len(string2)\n",
    "    if len(string2) == 0: return len(string1)\n",
    "    \n",
    "    tail_s1 = string1[-1]\n",
    "    tail_s2 = string2[-1]\n",
    "    \n",
    "    candicates = [\n",
    "        (edit_distance(string1[:-1], string2) + 1, 'DEL {}'.format(tail_s1)),\n",
    "        (edit_distance(string1, string2[:-1]) + 1, 'ADD {}'.format(tail_s2)),\n",
    "    ]\n",
    "    \n",
    "    if tail_s1 == tail_s2:\n",
    "        both_forward = (edit_distance(string1[:-1], string2[:-1]) + 0, '')\n",
    "    else:\n",
    "        both_forward = (edit_distance(string1[:-1], string2[:-1]) + 1, 'SUB {} => {}'.format(tail_s1, tail_s2))\n",
    "        \n",
    "    candicates.append(both_forward)\n",
    "    \n",
    "    min_distance, operation = min(candicates, key=lambda x: x[0])\n",
    "    \n",
    "    solution[(string1, string2)] = operation\n",
    "    \n",
    "    return min_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance('ABCDE', 'ABCCEF')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('A', 'A'): '',\n",
       " ('A', 'AB'): 'ADD B',\n",
       " ('A', 'ABC'): 'ADD C',\n",
       " ('A', 'ABCC'): 'ADD C',\n",
       " ('A', 'ABCCE'): 'ADD E',\n",
       " ('A', 'ABCCEF'): 'ADD F',\n",
       " ('AB', 'A'): 'DEL B',\n",
       " ('AB', 'AB'): '',\n",
       " ('AB', 'ABC'): 'ADD C',\n",
       " ('AB', 'ABCC'): 'ADD C',\n",
       " ('AB', 'ABCCE'): 'ADD E',\n",
       " ('AB', 'ABCCEF'): 'ADD F',\n",
       " ('ABC', 'A'): 'DEL C',\n",
       " ('ABC', 'AB'): 'DEL C',\n",
       " ('ABC', 'ABC'): '',\n",
       " ('ABC', 'ABCC'): 'ADD C',\n",
       " ('ABC', 'ABCCE'): 'ADD E',\n",
       " ('ABC', 'ABCCEF'): 'ADD F',\n",
       " ('ABCD', 'A'): 'DEL D',\n",
       " ('ABCD', 'AB'): 'DEL D',\n",
       " ('ABCD', 'ABC'): 'DEL D',\n",
       " ('ABCD', 'ABCC'): 'SUB D => C',\n",
       " ('ABCD', 'ABCCE'): 'ADD E',\n",
       " ('ABCD', 'ABCCEF'): 'ADD F',\n",
       " ('ABCDE', 'A'): 'DEL E',\n",
       " ('ABCDE', 'AB'): 'DEL E',\n",
       " ('ABCDE', 'ABC'): 'DEL E',\n",
       " ('ABCDE', 'ABCC'): 'DEL E',\n",
       " ('ABCDE', 'ABCCE'): '',\n",
       " ('ABCDE', 'ABCCEF'): 'ADD F'}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edit_distance('12345', '54321')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('1', '5'): 'SUB 1 => 5',\n",
       " ('1', '54'): 'ADD 4',\n",
       " ('1', '543'): 'ADD 3',\n",
       " ('1', '5432'): 'ADD 2',\n",
       " ('1', '54321'): '',\n",
       " ('12', '5'): 'DEL 2',\n",
       " ('12', '54'): 'SUB 2 => 4',\n",
       " ('12', '543'): 'ADD 3',\n",
       " ('12', '5432'): '',\n",
       " ('12', '54321'): 'ADD 1',\n",
       " ('123', '5'): 'DEL 3',\n",
       " ('123', '54'): 'DEL 3',\n",
       " ('123', '543'): '',\n",
       " ('123', '5432'): 'ADD 2',\n",
       " ('123', '54321'): 'ADD 1',\n",
       " ('1234', '5'): 'DEL 4',\n",
       " ('1234', '54'): '',\n",
       " ('1234', '543'): 'DEL 4',\n",
       " ('1234', '5432'): 'SUB 4 => 2',\n",
       " ('1234', '54321'): 'ADD 1',\n",
       " ('12345', '5'): '',\n",
       " ('12345', '54'): 'DEL 5',\n",
       " ('12345', '543'): 'DEL 5',\n",
       " ('12345', '5432'): 'DEL 5',\n",
       " ('12345', '54321'): 'SUB 5 => 1'}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
